"""
A Python implementation of the Probabilistic lossy counting algorithm.

"""
import fileinput
import math


def approximate_frequencyCounting(min_support,error_bound_percentage,train_dataset_path,test_dataset_path,no_of_recommendations):
    
    MIN_SUPPORT=min_support
    ERROR_BOUND=MIN_SUPPORT*error_bound_percentage/100
    BUCKET_SIZE=math.ceil(1/ERROR_BOUND)
    itemset={} # a frequency-list data structure 
    itemset=train(BUCKET_SIZE,train_dataset_path,itemset)
    test(test_dataset_path,itemset,no_of_recommendations)

def train(BUCKET_SIZE,train_dataset_path,itemset):
    bucket_count=1
    count=0
    session_count=1
    value=()
    for session in fileinput.input([train_dataset_path]):
        session_count=session_count+1
        session= session.strip().rstrip(',')
        item_list=session.split(',')
        item_tuple=tuple(item_list)
        if((session_count%BUCKET_SIZE)==0):
            bucket_count+=1
            itemset=prune(itemset,bucket_count)

        if(itemset.has_key(item_tuple)):
            value=itemset.get(item_tuple)
            count=value[0]
            count+=1
            itemset[item_tuple]=(count,(bucket_count-1))   
        else:
            itemset[item_tuple]=(1,(bucket_count-1))
    return itemset
                
                
def test(test_dataset_path,itemset,no_of_recommendations):
    recommendation_count=0
    accuracy=0
    coverage=0
    number_of_request=0
    for line in fileinput.input([test_dataset_path]): 
        line= line.strip().rstrip(',')
        session=line.split(',')
        length_of_session=len(session)-1 
        for i in range(0,length_of_session):
            number_of_request+=1
            j=i+1
            recommend_list=recommend(session[0:j],itemset,no_of_recommendations)
            length_of_recommendation_list=len(recommend_list)
            if not length_of_recommendation_list==0:
                recommendation_count+=1
                results=evaluate(recommend_list,session[j],recommendation_count,accuracy)   
                accuracy=results[0]
                coverage = float(float(recommendation_count)/float(number_of_request))
                print "-----------------------"
                print "Accuracy:", accuracy
                print "Coverage:",coverage
                print "------------------------"
            
def prune(itemset,bucket_size):
    '''
    This method will prune the dictionary of itemset of a specific item/itemset does not 
    adhere to certain condition:
    If  frequency + max _error <=bucket size ---> prune
    otherwise keep it in the dictionary
    '''
    print "Before Pruning No. of itemsets:",len(itemset)
    for key in itemset.keys():
        value=itemset.get(key)
        frequency=value[0]
        error=value[1]
        if((frequency+error)<=bucket_size):
            del itemset[key] 
    print "After Pruning No. of itemsets::",len(itemset)
    return itemset
        
def recommend(access_upto,itemset,no_of_recommendations):
    '''
    This method generate recommendations based on the session up to now by matching
    it with the frequent itemsets genrated in training
    '''
    length=len(access_upto)
    recommend_list=[]
    recommend_dic={}
    for key in itemset.keys():
        item_tuple=itemset.get(key)
        item_count=item_tuple[0]
        item_list=list(key)
        results_tuple=sublist(access_upto,item_list)
        index=results_tuple[1]+length
        if(results_tuple[0]==1 and (len(item_list)>index)):
            recommend_dic[item_list[index]]=item_count
        recommend_list=sorted(recommend_dic.iteritems(), key=lambda (k,v): (v,k)) # sorting the dictionary based on count
    recommend_list.reverse()
    lenth_of_recList=len(recommend_list)
    resultlist=[]
    for u in range(0,lenth_of_recList):
        resultlist.append((recommend_list[u])[0])
    return resultlist[0:no_of_recommendations]


def sublist(access_upto,itemlist):
    '''
    This method identify whether 1st list is a subset of 2nd list
    '''
    output=0
    index=0
    for i in range(0, len(itemlist)):
        if(itemlist[i]==access_upto[0]):
            index=i
            k=0
            if((i+len(access_upto)<=len(itemlist))):
                for j in range(i,i+len(access_upto)):
                    if(itemlist[j]==access_upto[k]):
                        output=1
                    else:
                        output=0
                        break
                    k+=1
            else:
                output=0
            break
                               
    return output,index

def evaluate(recommendationlist,actual,count,accuracy):
    '''
    This method evaluate the recommendations and returns the accuracy value
    '''
    correct=0
    if actual in recommendationlist:
        accuracy = calculate_accuracy(1,accuracy,count)
        return (accuracy,count,correct)
    else:
        accuracy=calculate_accuracy(0,accuracy,count)
        return (accuracy,count,correct)
    
def calculate_accuracy(correct,accuracy,count):
        return ((int(count)-1)*float(accuracy)+int(correct))/int(count)

if __name__ == "__main__": approximate_frequencyCounting(0.01,10,'D:\\A_1.txt','D:\\A_2.txt',20)
